Chihik's Blog

An Ac a day, keeps the doctor away!

P3911 最小公倍数之和

发布于 2020-09-12 | 分类于 莫比乌斯反演 | 5分钟 | 817字数

简单问题复杂化是解决问题的一个好方法。

令 cic_i 表示 ii 出现的次数，nn 为最大数字。

∑i=1n∑j=1nci×cj×lcm(i,j)\sum_{i=1}^n \sum_{j=1}^nc_i \times c_j \times lcm(i,j)

阅读全文 »

P6156 简单题

发布于 2020-09-12 | 分类于 莫比乌斯反演 | 6分钟 | 983字数

∑i=1n∑j=1n(i+j)kf(gcd⁡(i,j))gcd⁡(i,j)\sum_{i=1}^n \sum_{j=1}^n (i+j)^k f(\gcd(i,j)) \gcd(i,j)

显然 f(i)=μ2(i)f(i)=\mu^2(i)

阅读全文 »

P4619 [SDOI2018]旧试题

发布于 2020-09-12 | 分类于 莫比乌斯反演 | 9分钟 | 1353字数

∑i=1A∑j=1B∑k=1Cd(ijk)\sum_{i=1}^A\sum_{j=1}^B\sum_{k=1}^Cd(ijk)

∑i=1A∑j=1B∑k=1C∑x∣i∑y∣j∑z∣k[(x,y)=1][(y,z)=1][(x,z)=1]\sum_{i=1}^A\sum_{j=1}^B\sum_{k=1}^C\sum_{x|i}\sum_{y|j}\sum_{z|k}[(x,y)=1][(y,z)=1][(x,z)=1]

阅读全文 »

P1587 [NOI2016]循环之美

发布于 2020-09-12 | 分类于 莫比乌斯反演 | 5分钟 | 764字数

类比十进制下的纯循环小数，kk 进制下的纯循环小数满足最简分数分母与 kk 互质。

而题目要求相同数值只计数一次，所以只需要考虑最简分数的情况。

那么答案为：

阅读全文 »

P2480 [SDOI2010]古代猪文

发布于 2020-09-12 | 分类于 数论 | 4分钟 | 515字数

g∑d∣nCnn/dmod  999911659g^{\sum_{d|n}C_{n}^{n/d}} \mod 999911659

g∑d∣nCndmod  999911659g^{\sum_{d|n}C_{n}^{d}} \mod 999911659

阅读全文 »
0%